package com.leetcodehot.problems;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class problems981 {
    /**
     * 设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
     * <p>
     * 实现 TimeMap 类：
     * <p>
     * TimeMap() 初始化数据结构对象
     * void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
     * String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。如果有多个这样的值，它将返回与最大  timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。
     */
    class TimeMap {
        HashMap<String, List<Integer>> map = new HashMap<>();
        HashMap<String, String> timeAddKeyMap = new HashMap<>();

        public TimeMap() {

        }

        public void set(String key, String value, int timestamp) {
            List<Integer> list;
            if (map.containsKey(key)) {
                list = map.get(key);
                list.add(timestamp);
                timeAddKeyMap.put(timestamp + "_" + key, value);
            } else {
                list = new ArrayList<>();
                list.add(timestamp);
                map.put(key, list);
                timeAddKeyMap.put(timestamp + "_" + key, value);
            }
        }

        public String get(String key, int timestamp) {
            if (map.containsKey(key)) {
                List<Integer> list = map.get(key);
                int n = list.size();
                int left = -1;
                int right = n;
                while (left + 1 < right) {
                    int mid = left + (right - left) / 2;
                    if (list.get(mid) <= timestamp) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                } // left
                if (left == -1)
                    return "";
                return timeAddKeyMap.get(list.get(left) + "_" + key);
            }
            return "";
        }
    }

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */
}
